//
// Created by cheng on 2021/02/21.
//

#include <iostream>
#include <vector>

using namespace std;

void QuickSort(vector<int>& list, int left, int right);

int Partition(vector<int>& arr, int left, int right);

int RandomPartition(vector<int>& list, int left, int right);

int main() {
    vector<int> arr = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
    QuickSort(arr, 0, arr.size()-1);
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

void QuickSort(vector<int>& list, int left, int right) {
    if (left < right) {
        int pos = RandomPartition(list, left, right); // 随机数组划分
        QuickSort(list, left, pos); // 递归处理左边的数据
        QuickSort(list, pos + 1, right); // 递归处理右边的数据
    }
}

int Partition(vector<int> &arr, int left, int right) {
    int i = left, j = right+1;
    int pos = left; // 哨兵坐标
    int posValue = arr[pos];
    while (true) {
        while (arr[++i] < posValue && i < j);
        while (arr[--j] > posValue);
        if(i > j) {
            break;
        }
        swap(arr[i], arr[j]);
    }
    arr[pos] = arr[j];
    arr[j] = posValue;
    return j;
}

int RandomPartition(vector<int>& list, int left, int right) {
    if (left < right) {
        int pos = (int)(rand() % (right - left) + left);; // 哨兵坐标
        swap(list[pos], list[left]);
        return Partition(list, left, right);
    }
    return -1;
}
